Robust computation of linear models by convex relaxation

摘要

Consider a dataset of vector-valued observations that consists of noisyinliers, which are explained well by a low-dimensional subspace, along withsome number of outliers. This work describes a convex optimization problem,called REAPER, that can reliably fit a low-dimensional model to this type ofdata. This approach parameterizes linear subspaces using orthogonal projectors,and it uses a relaxation of the set of orthogonal projectors to reach theconvex formulation. The paper provides an efficient algorithm for solving theREAPER problem, and it documents numerical experiments which confirm thatREAPER can dependably find linear structure in synthetic and natural data. Inaddition, when the inliers lie near a low-dimensional subspace, there is arigorous theory that describes when REAPER can approximate this subspace.